#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/15
# @Author   :Changshu
# @File     :Exercise_589.py
# 589. N叉树的前序遍历
# 给定一个 N 叉树，返回其节点值的前序遍历。

# Definition for a Node.
class Node:
	def __init__(self, val=None, children=None):
		self.val = val
		self.children = children


class Solution:
	'''法一：递归实现，比较简单
	def preorder(self, root: 'Node') -> list:
		res = []
		def helper(root:'Node'):
			if not root:
				return
			res.append(root.val)
			for n in root.children:
				helper(n)
		helper(root)
		return res
	'''

	'''法二：使用栈进行迭代'''
	def preorder(self, root: 'Node') -> list:
		if not root:
			return
		stack,res=[root],[]
		while stack:
			node=stack.pop()
			res.append(node.val)
			stack.extend(node.children[::-1])
		return res


if __name__ == '__main__':
	root=Node(val=1,children=[])
	node2_1 = Node(val=3,children=[])
	node2_2 = Node(val=2,children=[])
	node2_3 = Node(val=4,children=[])
	node3_1 = Node(val=5,children=[])
	node3_2 = Node(val=6,children=[])

	root.children.append(node2_1)
	root.children.append(node2_2)
	root.children.append(node2_3)

	node2_1.children.append(node3_1)
	node2_1.children.append(node3_2)

	solution=Solution()
	print(solution.preorder(root))